package com.mlh.binarytree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author 缪林辉
 * @date 2024/3/28 9:40
 * @DESCRIPTION
 */

// 给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
// 输入: [1,2,3,4,null,5,6,null,null,7]
// 输出: 7
public class FindBottomLeftValue {
    //利用BFS 每次层遍历的第一个节点  就是该层的最左节点
    public int method1(TreeNode root) {
        Deque<TreeNode> treeNodes = new LinkedList<>();
        treeNodes.add(root);
        int res = Integer.MIN_VALUE;
        while(!treeNodes.isEmpty()){
            int len=treeNodes.size();
            res=treeNodes.peek().val;
            while (len>0){
                TreeNode node=treeNodes.poll();
                len--;
                if(node.left!=null){
                    treeNodes.add(node.left);
                }
                if(node.right!=null){
                    treeNodes.add(node.right);
                }
            }
        }
        return res;
    }

    //利用DFS 当某个节点深度最深时就是答案
    //当很多节点深度都一样时,DFS先遍历到的一定是最左节点
    int res=Integer.MIN_VALUE;//结果
    int maxHeight=0;//最深层
    public int method2(TreeNode root) {
        recursion(root,1);
        return res;
    }

    public void recursion (TreeNode node,int height){
        if(node==null){
            return;
        }
        //有更深的就更新
        if(height>maxHeight){
            maxHeight=height;
            res=node.val;
        }
        recursion(node.left,height+1);
        recursion(node.right,height+1);
    }
}
